Structure Array2

(* Array2 -- SML Basis Library *)

eqtype 'a array2

val array      : int * int * '_a -> '_a array2
val fromList   : '_a list list -> '_a array2
val tabulate   : int * int * (int * int -> '_a) -> '_a array2

val dimensions : 'a array2 -> int * int
val width      : 'a array2 -> int
val height     : 'a array2 -> int

val sub        : 'a array2 * int * int -> 'a
val update     : 'a array2 * int * int * 'a -> unit

val row        : 'a array2 * int -> 'a Vector.vector
val column     : 'a array2 * int -> 'a Vector.vector

type region = { row : int, col : int, ht : int option, wd : int option}
datatype traversal = RowMajor | ColMajor

val copy       : { src : 'a array2, dst : 'a array2, src_reg : region, 
		   dst_row : int, dst_col : int } -> unit

val app        : ('a -> unit) -> 'a array2 -> unit
val modify     : ('a -> 'a) -> 'a array2 -> unit
val fold       : traversal -> ('a * 'b -> 'b) -> 'b -> 'a array2 -> 'b

val appi       : (int * int * 'a -> unit) -> 'a array2 * region -> unit
val modifyi    : (int * int * 'a -> 'a) -> 'a array2 * region -> unit
val foldi      : traversal -> (int * int * 'a * 'b -> 'b) -> 'b 
                 -> 'a array2 * region -> 'b


(* Type [ty array2] is the type of two-dimensional, mutable,
   zero-based constant-time-access arrays with elements of type ty.
   Type ty array admits equality even if ty does not.  Arrays a1 and
   a2 are equal if both were created by the same call to one of the
   primitives array, fromList, and tabulate.

   [array(m, n, x)] returns a new m * n matrix whose elements are all x.  
   Raises Size if n<0 or m<0.

   [fromlist xss] returns a new array whose first row has elements
   xs1, second row has elements xs2, ..., where xss = [xs1,xs2,...,xsm].  
   Raises Size if the lists in xss do not all have the same length.

   [tabulate(m, n, f)] returns a new m-by-n array whose elements
   are f(0,0), f(0,1), ..., f(0, n-1), 
       f(1,0), f(1,1), ..., f(1, n-1),
                    ...
       f(m-1,0),    ...,    f(m-1, n-1)
   created in that order.  Raises Size if n<0 or m<0.

   [dimensions a] returns the dimensions (m, n) of a, where m is the
   number of rows and n the number of columns.

   [width a] returns the number of n of columns of a.

   [height a] returns the number of m of rows of a.

   [sub(a, i, j)] returns the i'th row's j'th element, counting from 0.
   Raises Subscript if i<0 or j<0 or i>=m or j>=n 
   where (m,n) = dimensions a.

   [update(a, i, j, x)] destructively replaces the (i,j)'th element of a 
   by x. Raises Subscript if i<0 or j<0 or i>=m or j>=n 
   where (m,n) = dimensions a. 

   [row (a, i)] returns a vector containing the elements of the ith
   row of a.  Raises Subscript if i < 0 or i >= height a.

   [column (a, j)] returns a vector containing the elements of the jth
   column of a.  Raises Subscript if j < 0 or j >= width a.

   [app f a] applies f to the elements a[0,0], a[0,1], ..., a[0,n-1],
   a[1,0], ..., a[m-1, n-1] of a, where (m, n) = dimensions a.

   [modify f a] applies f to the elements a[0,0], a[0,1], ..., a[0,n-1], 
   a[1,0], ..., a[m-1, n-1] of a, updating each element with the
   result of the application, where (m, n) = dimensions a.

   [fold RowMajor f b a] folds f left-right and top-down over the
   elements of in row-major order.  That is, computes
	f(a[m-1, n-1], f(a[m-1, n-2], ..., f(a[0,1], f(a[0,0], b)) ...))
   where (m, n) = dimensions a.

   [fold ColMajor f b a] folds f left-right and top-down over the
   elements of a in column-major order.  That is, computes
	f(a[m-1, n-1], f(a[m-2, n-1], ..., f(a[1,0], f(a[0,0], b)) ...))
   where (m, n) = dimensions a.


   The following iterators generalize the above ones in two ways:

     . the indexes i and j are also being passed to the function;
     . the iterators work on a region (submatrix) of a matrix.          

   The region { row, col, ht, wd } determines a region or submatrix
   whose upper left corner has index (row, col).  
   If ht = SOME h, then the region has h rows: row, row+1, ..., row+h-1.
   If ht = NONE, then the region extends to the bottom of the matrix.
   The field wd similarly determines the number of columns.

   A region is valid for an array with dimensions (m, n) if 
       (1) either ht = NONE and 0 <= row <= m 
           or ht = SOME h and 0 <= row <= row + h <= m 
   and (2) either wd = NONE and 0 <= col <= n
           or wd = SOME w and 0 <= col <= col + w <= n.

   [appi f (a, reg)] applies f to (i, j, a[i, j]) for lexicographically 
   increasing (i, j) within the region reg.  Raises Subscript if reg is 
   not valid.  Note that app f a has the same effect as 
   appi (f o #3) (a, {row=0, col=0, ht=NONE, wd=NONE}).

   [modifyi f (a, reg)] applies f to (i, j, a[i, j]) for lexicographically 
   increasing (i, j) within the region reg.  Raises Subscript if reg is 
   not valid.  Note that modify f a has the same effect as 
   modifyi (f o #3) (a, {row=0, col=0, ht=NONE, wd=NONE}).

   [foldi RowMajor f b a] folds f over (i, j, a[i, j]) in row-major
   order within the region reg, that is, for lexicographically
   increasing (i, j) in the region.  Raises Subscript if reg is not
   valid.

   [foldi ColMajor f b a] folds f over (i, j, a[i, j]) in column-major
   order within the region reg, that is, for lexicographically
   increasing (j, i) in the region.  Raises Subscript if reg is not
   valid.

   [copy { src, dst, src_reg, dst_row, dst_col }] copies the region
   src_reg from array src to array dst, such that the upper leftmost
   corner of src_reg is copied to dst[dst_row, dst_col].  Works
   correctly even when src and dst are the same and the source region
   overlaps with the destination region.  Raises Subscript if the
   region src_reg is invalid for src, or if src_reg translated to
   (dst_row, dst_col) is invalid for dst.

*)